//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//#define lc (2*p)
//#define rc (2*p+1)
//
//const int N = 1e6 + 5;
//int a[N];
//
//struct node
//{
//	int l;
//	int r;
//	ll max;
//	ll add;
//}tr[4 * N];
//
//void pushup(int p)
//{
//	tr[p].max = max(tr[lc].max, tr[rc].max);
//}
//
//void pushdown(int p)
//{
//	if (tr[p].add)
//	{
//		tr[lc].add += tr[p].add;
//		tr[rc].add += tr[p].add;
//		tr[p].add = 0;
//	}
//}
//
//void bulid(int p, int l, int r)
//{
//	tr[p] = { l, r, a[l], 0 };
//	if (l == r)
//		return;
//	
//	int mid = (l + r) / 2;
//	bulid(lc, l, mid);
//	bulid(rc, mid + 1, r);
//	pushup(p);
//}
//
//ll query(int p, int x, int y)
//{
//	if (tr[p].l >= x && tr[p].r <= y)
//	{
//		return tr[p].max;
//	}
//
//	int mid = (tr[p].l + tr[p].r) / 2;
//	ll maxx = INT_MIN;
//	if (x <= mid)
//		maxx = query(lc, x, y);
//	if (y > mid)
//		maxx = max(maxx, query(rc, x, y));
//
//	return maxx;
//}
//
////void change(int p, int x, int y, int k)
////{
////	if (tr[p].l >= x && tr[p].r <= y)
////	{
////		tr[p].max = k;
////		tr[p].add = 0;
////		return;
////	}
////
////	int mid = (tr[p].l + tr[p].r) / 2;
////	pushdown(p);
////	if (x <= mid)
////		change(lc, x, y, k);
////	if (y > mid)
////		change(rc, x, y, k);
////
////	return;
////}
//
//void change(int p, int x, int y, int k)
//{
//	if (tr[p].l >= x && tr[p].r <= y)
//	{
//		a[tr[p].l] = k;
//		a[tr[p].r] = k;
//		tr[p].max = k;
//		tr[p].add = 0;
//		
//		if (tr[p].l == tr[p].r)
//			return;
//	}
//
//	int mid = (tr[p].l + tr[p].r) / 2;
//	pushdown(p);
//	if (x <= mid)
//		change(lc, x, y, k);
//	if (y > mid)
//		change(rc, x, y, k);
//	pushup(p);
//	return;
//}
//
//
//void add(int p, int x, int y, int k)
//{
//	if (tr[p].l >= x && tr[p].r <= y)
//	{
//		tr[p].add += k;
//		tr[p].max += k;
//		return;
//	}
//
//	int mid = (tr[p].l + tr[p].r) / 2;
//	pushdown(p);
//	if (x <= mid)
//		add(lc, x, y, k);
//	if (y > mid)
//		add(rc, x, y, k);
//	return;
//}
//
//int main()
//{
//	quickio;
//	int n, q;
//	cin >> n >> q;
//	int op = 0;
//	for (int i = 1; i <= n; i++)
//		cin >> a[i];
//	bulid(1, 1, n);
//	int l, r, k;
//	while (q--)
//	{
//		cin >> op;
//		if (op == 1)
//		{
//			cin >> l >> r >> k;
//			change(1, l, r, k);
//		}
//		else if (op == 2)
//		{
//			cin >> l >> r >> k;
//			add(1, l, r, k);
//		}
//		else
//		{
//			cin >> l >> r;
//			cout << query(1, l, r) << endl;
//		}
//	}
//	return 0;
//}